Euler Tour Technique

여러버전이 있는데, 3개의 위치(dfs를 들어올때, 자식노드 처리후 돌아왔을때, dfs나갈때)에서 저장하는지 여부로 나눌 수 있다. 크게 두가지 버전이 있는데, 세가지 위치에서 전부 다 표시하는것과, 들어올때만 표시해두고 subtree size를 사용해서 쿼리하는 버전이다.

이 트릭으로 트리를 배열로 펼쳐서 표현하면 몇가지 유용한 성질을 가진다.

1. 서브트리의 노드들 위치가 배열에서 연속한다.

2. 두 노드 사이의 제일 깊지않은 노드가 LCA이다.(ver1)

이중에서 1번 성질이 아주 유용한데, 저것덕분에 서브트리 쿼리는 많은 경우 오일러 투어로 펼친 배열위에서 쿼리로 변환이 가능해진다.

ver1: 들어올때, 중간, 나갈때 전부 기록

ver2: 들어올때만 기록, pre-order

ver3: 나갈때만 기록, post-order

ver2와 ver3에서는 보통 각 노드의 subtree size도 관리해준다. 그리고 subtree에 해당하는 구간은 [x2pre[x],x2pre[x]+tsz[x])형태로 나온다.